package com.bootcamp.s2_0922.ds.Exercise._0926_Ex;

import static jdk.nashorn.internal.objects.NativeMath.min;

/**
 * @program: myClassCode
 * @description: judge a tree whether is a BST or not
 * @author: Keyu Li
 * @create: 2021-09-26 20:28
 **/

public class Ex2_Tree {
    public static void main(String[] args) {
        // 判断是否是 二叉树
        Node root = createTreeBST();
        boolean isBST = judgeTree(root);
        if (isBST)
            System.out.println("is binary search tree!");
        else
            System.out.println("is not binary searcb tree!");

        // 判断是否是镜像树、
        root = createTreeMirror();
        boolean isMirror = judgeMirrorTree(root);
        // 反转树
        reverseTree(root);
    }

    // 递归逆转二叉树
    private static void reverseTree(Node root) {
        if (root.lchild == null && root.rchild == null) return;
        // 上层先翻转
        Node temp = root.lchild;
        root.lchild = root.rchild;
        root.rchild = temp;
        // 下层翻转
        reverseTree(root.lchild);
        reverseTree(root.rchild);
        return;
    }


    private static boolean judgeMirrorTree(Node root) {
        // 将根节点分裂为两个节点：左根节点和右根节点
        return judgeMirrorTreeHelper(root, root);
    }

    private static boolean judgeMirrorTreeHelper(Node lnode, Node rnode) {
        // lnode代表根节点左子树的节点，rnode代表根节点右子树的节点
        if (lnode.lchild!=null) {
            if (rnode.rchild!=null) {
                if (lnode.lchild.value.equals(rnode.rchild.value))
                    return judgeMirrorTreeHelper(lnode.lchild,rnode.rchild);
            }
            return false;
        }
        if (lnode.rchild!=null) {
            if (rnode.lchild!=null) {
                if (lnode.rchild.value.equals(rnode.lchild.value))
                    return judgeMirrorTreeHelper(lnode.rchild,rnode.lchild);
            }
            return false;
        }
        return true;
    }


    // 递归判断是否是二叉搜索树：只有一个节点true
    private static boolean judgeTree(Node root) {
        if (root.lchild == null && root.rchild == null) return true;
        if (root.lchild != null && root.value.compareTo(max(root.lchild)) > 0) {
            return judgeTree(root.lchild);
        }
        if (root.rchild != null && root.value.compareTo(min(root.rchild)) < 0) {
            return judgeTree(root.rchild);
        }
        return false;
    }

    // 从底向上，把已经判断的正确的子树当作节点，向上继续判断
    private static Object max(Node node) {
        while (node.rchild!=null){
            node = node.rchild;
        }
        return node.value;
    }

    private static Object min(Node node) {
        while (node.lchild!=null){
            node = node.lchild;
        }
        return node.value;
    }


    private static Node createTreeMirror() {
        return null;
    }

    private static Node createTreeBST() {
        return null;
    }
}

class Node<T extends Comparable<T>> {
    T value;
    Node lchild;
    Node rchild;

    public Node(T value, Node lchild, Node rchild) {
        this.value = value;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}